#include <cassert>
#include <cstdio>

/// 传统的递归式求解
static int bad_fib(int n) {
    assert (n > 0 && n <= 50);
    if (n <= 2)
        return 1; 
    return bad_fib(n-1) + bad_fib(n-2);
}

/// 缓存了以前计算过的数据，以空间换时间
static int good_fib(int n) {
    static int table[10000] {1,1};
    assert (n > 0 && n <= 10000);
    if (table[n-1] == 0) {
        table[n-1] = good_fib(n-1) + good_fib(n-2);
    }
    return table[n-1];
}

int main() {
    const int n = 45;
    int x = bad_fib(n);
    fprintf(stdout, "fib(%d)=%d\n", n, x);
    x = good_fib(n*2);
    fprintf(stdout, "fib(%d)=%d\n", n*10, x);
}